The World Wide Web makes it possible to exchange and integrate data on an unprecedented scale. A natural question in connection with data exchange and integration concerns whether dependencies that hold on data sources still hold on the target data (i.e., data transformed via mapping from the sources). As dependencies (often referred to as integrity constraints) specify a fundamental part of the semantics of the data, one wants to know whether or not the dependencies are propagated from the sources via the mapping, i.e., whether the mapping preserves information.
The dependency propagation problem determines, given a view (mapping) defined on data sources and dependencies that hold on the sources, whether or not another dependency is guaranteed to hold on the view. The dependencies defined on the sources are referred to as source dependencies, and those on the view are referred to as as view dependencies.
The dependency propagation problem has been extensively studied when source and view dependencies are functional dependencies (FDs), for views defined in relational algebra. It has been found that while many source FDs may not hold on the view as they are, they do hold on the view under conditions. In other words, source FDs are indeed propagated to the view, not as standard FDs but as FDs with conditions. The FDs with conditions are in the form of conditional functional dependencies (CFDs). See, U.S. patent application Ser. No. 12/411,935, filed Mar. 26, 2009, entitled “Methods and Apparatus for Identifying Conditional Functional Dependencies,” incorporated by reference herein. While the implication and consistency problems for CFDs are addressed, the propagation problem is not considered.
A need therefore exists for methods and apparatus for computing a propagation cover for conditional functional dependencies.